package algorithm.arrayAlgorithm;

import java.util.*;

/**
 * @ClassName: CanReorderDoubled
 * @Description 954. 二倍数对数组
 * 给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <=i < len(arr) / 2，
 *
 * 都有 arr[2 * i + 1] = 2 * arr[2 * i]”时，返回 true；否则，返回 false。
 *
 * @Author skywingking
 * @Date 2022/4/1 9:34 下午
 **/
public class CanReorderDoubled {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer,Integer> cnt = new HashMap<>();
        for(int x : arr){
            cnt.put(x,cnt.getOrDefault(x,0) + 1);
        }
        if(cnt.getOrDefault(0,0) % 2 != 0){
            return false;
        }
        List<Integer> vals = new ArrayList<>();
        for(int x : cnt.keySet()){
            vals.add(x);
        }
        Collections.sort(vals,(a,b) -> Math.abs(a) - Math.abs(b));
        for(int x : vals){
            if(cnt.getOrDefault(2 * x,0) < cnt.get(x)){
                return false;
            }
            cnt.put(2 * x,cnt.getOrDefault(2 * x,0) - cnt.get(x));
        }
        return true;

    }
}